﻿namespace AdvancedTraining.Lesson35;

/// <summary>
/// 来自小红书的魔法石头问题
/// [0,4,7] ： 0表示这里石头没有颜色，如果变红代价是4，如果变蓝代价是7
/// [1,X,X] ： 1表示这里石头已经是红，而且不能改颜色，所以后两个数X无意义
/// [2,X,X] ： 2表示这里石头已经是蓝，而且不能改颜色，所以后两个数X无意义
/// 颜色只可能是0、1、2，代价一定>=0
/// 给你一批这样的小数组，要求最后必须所有石头都有颜色，且红色和蓝色一样多，返回最小代价
/// 如果怎么都无法做到所有石头都有颜色、且红色和蓝色一样多，返回-1
/// </summary>
public class MagicStone
{
    /// <summary>
    /// 计算魔法石头的最小代价
    /// 算法思路：
    /// 1. 如果石头总数为奇数，直接返回-1（无法平分红蓝）
    /// 2. 对石头进行排序：已着色的石头在前，未着色的石头在后
    /// 3. 对于未着色的石头，按照(变蓝代价 - 变红代价)降序排列，这样优先选择变蓝更便宜的石头
    /// 4. 统计已着色的红蓝石头数量，如果超出一半则无法完成
    /// 5. 计算需要将多少未着色石头变为蓝色，补齐平衡
    /// 6. 累加所有代价得到最终答案
    /// 时间复杂度：O(n log n)，空间复杂度：O(1)
    /// </summary>
    /// <param name="stones">石头数组，每个元素为[颜色,变红代价,变蓝代价]</param>
    /// <returns>最小代价，如果无法实现则返回-1</returns>
    public static int MinCost(int[][] stones)
    {
        var n = stones.Length;
        if ((n & 1) != 0) return -1;
        Array.Sort(stones, (a, b) => a[0] == 0 && b[0] == 0 ? b[1] - b[2] - a[1] + a[2] : a[0] - b[0]);
        var zero = 0;
        var red = 0;
        var blue = 0;
        var cost = 0;
        for (var i = 0; i < n; i++)
            if (stones[i][0] == 0)
            {
                zero++;
                cost += stones[i][1];
            }
            else if (stones[i][0] == 1)
            {
                red++;
            }
            else
            {
                blue++;
            }

        if (red > n >> 1 || blue > n >> 1) return -1;
        blue = zero - ((n >> 1) - red);
        for (var i = 0; i < blue; i++) cost += stones[i][2] - stones[i][1];
        return cost;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 魔法石头问题测试 ===");

        // 测试用例1：基本功能测试
        TestBasicFunctionality();

        // 测试用例2：奇数个石头
        TestOddStones();

        // 测试用例3：全部已着色且平衡
        TestAllColoredBalanced();

        // 测试用例4：全部未着色
        TestAllUncolored();

        // 测试用例5：无法平衡的情况
        TestImpossibleBalance();

        // 测试用例6：边界情况
        TestEdgeCases();
    }

    private static void TestBasicFunctionality()
    {
        int[][] stones =
        [
            [1, 5, 3],
            [2, 7, 9],
            [0, 6, 4],
            [0, 7, 9],
            [0, 2, 1],
            [0, 5, 9]
        ];
        int result = MinCost(stones);
        Console.WriteLine($"测试1 - 基本功能: 6个石头 -> {result} (期望: 17)");
    }

    private static void TestOddStones()
    {
        int[][] stones =
        [
            [1, 5, 3],
            [2, 7, 9],
            [0, 6, 4]
        ];
        int result = MinCost(stones);
        Console.WriteLine($"测试2 - 奇数个石头: 3个石头 -> {result} (期望: -1)");
    }

    private static void TestAllColoredBalanced()
    {
        int[][] stones =
        [
            [1, 5, 3],
            [2, 7, 9],
            [1, 4, 2],
            [2, 8, 6]
        ];
        int result = MinCost(stones);
        Console.WriteLine($"测试3 - 全部已着色且平衡: 4个石头(2红2蓝) -> {result} (期望: 0)");
    }

    private static void TestAllUncolored()
    {
        int[][] stones =
        [
            [0, 1, 2],
            [0, 3, 1],
            [0, 2, 4],
            [0, 5, 3]
        ];
        int result = MinCost(stones);
        Console.WriteLine($"测试4 - 全部未着色: 4个石头 -> {result} (期望: 7)");
    }

    private static void TestImpossibleBalance()
    {
        int[][] stones =
        [
            [1, 5, 3],
            [1, 4, 2],
            [1, 6, 4],
            [0, 1, 2]
        ];
        int result = MinCost(stones);
        Console.WriteLine($"测试5 - 无法平衡: 3红1无色 -> {result} (期望: -1)");
    }

    private static void TestEdgeCases()
    {
        int[][] stones =
        [
            [0, 0, 0],
            [0, 0, 0]
        ];
        int result = MinCost(stones);
        Console.WriteLine($"测试6 - 边界情况: 2个无代价石头 -> {result} (期望: 0)");
    }
}